package com.xinwei.leetcode.二叉树;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
public class _144_二叉树的前序遍历 {
    // 递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        preorderTraversal(root, list);
        return list;
    }

    private void preorderTraversal(TreeNode node, List<Integer> list) {
        if (node == null) return;
        list.add(node.val);
        preorderTraversal(node.right, list);
        preorderTraversal(node.left, list);
    }


    // 栈迭代实现
    public List<Integer> preorderTraversal1(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                list.add(root.val);
                if (root.right != null) deque.push(root.right);
                root = root.left;
            }
            if (!deque.isEmpty()) root = deque.pop();
        }
        return list;
    }
}
